package com.leetcode.根据算法进行分类.滑动窗口相关;

/**
 * @author: ZhouBert
 * @date: 2021/3/24
 * @description: 456. 132模式
 * https://leetcode-cn.com/problems/132-pattern/
 */
public class B_456_132模式 {

	static B_456_132模式 action = new B_456_132模式();

	public static void main(String[] args) {
//		test1();
//		test2();
		test3();
	}

	static void test1() {
		int[] nums = new int[]{3, 1, 4, 2};
		boolean res = action.find132patternByGreedyFail(nums);
		System.out.println("res = " + res);
	}

	/**
	 * BUG 1
	 */
	static void test2() {
		int[] nums = new int[]{3, 5, 0, 3, 4};
		boolean res = action.find132patternByGreedyFail(nums);
		System.out.println("res = " + res);
	}

	static void test3() {
		int[] nums = new int[]{1, 4, 0, -1, -2, -3, -1, -2};
		boolean res = action.find132patternBySlideWindow(nums);
		System.out.println("res = " + res);
	}

	/**
	 * 由于只要返回是否即可，那么具有普遍的规律。
	 * 我理解的132，就是找到左边的 min1 ，然后再右边找到相对的 max，然后再找到右边的 min2 > min1
	 * --
	 * 这样似乎不对，思路不对。
	 * 因为不好抉择更新的时机
	 *
	 * @param nums
	 * @return
	 */
	public boolean find132patternFail(int[] nums) {
		//表示状态：0-找到 min1 ;1-找到 max;2-找到 min2
		int flag = 0;
		int len = nums.length;
		if (len < 3) {
			return false;
		}
		int min1 = nums[0], max = 0, min2 = 0;
		for (int i = 1; i < len; i++) {

		}
		return true;
	}

	/**
	 * 这种贪心的思路有问题！
	 *
	 * @param nums
	 * @return
	 */
	public boolean find132patternByGreedyFail(int[] nums) {
		int len = nums.length;
		if (len < 3) {
			return false;
		}
		//滑动数组，记录 候选 132
		int[] slideArr = new int[3];
		slideArr[1] = 1;
		slideArr[2] = 2;
		if (check(slideArr, nums)) {
			return true;
		}
		//记录老的
		int[] slideOldArr = new int[3];
		slideOldArr[1] = 1;
		slideOldArr[2] = 2;
		for (int i = 3; i < len; i++) {
			if (nums[i] < nums[slideArr[2]] || (nums[i] > nums[slideArr[0]] && nums[slideArr[1]] > nums[i])) {
				//如果当前索引小于 模式2 的位置 ||
				slideArr[2] = i;
			}
			if (slideArr[2] != slideOldArr[2]) {
				//如果已经更新 模式2 的位置
				if (nums[slideOldArr[2]] > nums[slideArr[1]]) {
					slideArr[1] = slideOldArr[2];
				}
				slideOldArr[2] = slideArr[2];
			}
			if (slideArr[1] != slideOldArr[1]) {
				//如果已经更新 模式3 的位置
				if (nums[slideOldArr[1]] < nums[slideArr[0]]) {
					slideArr[0] = slideOldArr[1];

					slideOldArr[0] = slideArr[0];
				}
				slideOldArr[1] = slideArr[1];
			}
			if (check(slideArr, nums)) {
				return true;
			}

		}
		return false;
	}

	private boolean check(int[] slideArr, int[] nums) {
		return nums[slideArr[2]] > nums[slideArr[0]] && nums[slideArr[1]] > nums[slideArr[2]];
	}

	/**
	 * 使用滑动窗口进行优化
	 *
	 * @param nums
	 * @return
	 */
	public boolean find132patternBySlideWindow(int[] nums) {
		int len = nums.length;
		if (len < 3) {
			return false;
		}
		int index1 = 0, index3 = 1, index2 = 2;
		//将 13 作为滑动窗口
		while (index3 < len) {
			if (nums[index1] >= nums[index3]) {
				index1 = index3;
				index3++;
				continue;
			}
			//此时 nums[index1] < nums[index3] 即 符合 13
			//然后去寻找 2 的位置
			index2 = index3 + 1;
			while (index2 < len) {
				if (nums[index2] < nums[index3] && nums[index2] > nums[index1]) {
					return true;
				}
				index2++;
			}

			if (nums[index1] > nums[index3]) {
				index1 = index3;
			}
			index3++;
		}

		return false;
	}
}
